package com.ww.springboot.boot.algorithm.list;

import java.util.Arrays;

/**
 * 小扣在秋日市集选择了一家早餐摊位，
 * 一维整型数组 staple 中记录了每种主食的价格，
 * 一维整型数组 drinks 中记录了每种饮料的价格。
 * 小扣的计划选择一份主食和一款饮料，且花费不超过 x 元。请返回小扣共有多少种购买方案。
 * <p>
 * 注意：答案需要以 1e9 + 7 (1000000007) 为底取模，如：计算初始结果为：1000000008，请返回 1
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/2vYnGI
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * <p>
 * 解题思路：
 * 1.暴力解题
 * 将两个数组遍历一遍 相加比较 返回符合要求的个数即可
 * <p>
 * 2.优化1 将两个数组排序可以减少不必要的遍历次数
 * <p>
 * 3.优化2 第一个数组正序 第二个数组倒序遍历 进一步减少次数
 *
 * @author wanwei
 * @since 2021-03-16 22:43
 */
public class BreakfastNumberDemo {

    public static void main(String[] args) {

        int[] a = {2, 1, 1};
        int[] b = {8, 9, 5, 1};

        System.out.println(method(a, b, 9));
    }

    public static int method(int[] staple, int[] drinks, int x) {
        Arrays.sort(staple);
        Arrays.sort(drinks);

        int total = 0;
        int jj = drinks.length - 1;

        for (int i = 0; i < staple.length; i++) {
            //如果 i>X 结束循环
            if (staple[i] > x) {
                break;
            }

            for (int j = jj; j >= 0; j--) {
                //如果 i+j <=X 则后面的所有结果都符合要求
                if (staple[i] + drinks[j] <= x) {
                    total += (j + 1);
                    total %= 1000000007;
                    jj = j;
                    break;
                }
                //如果j已经遍历完了 就不再继续了
                if(j == 0){
                    return total;
                }
            }
        }
        return total;
    }
}
